/*
 * @lc app=leetcode id=445 lang=cpp
 *
 * [445] Add Two Numbers II
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getLen(ListNode *node) {
        int len = 0;
        while(node) {
            node = node->next;
            len++;
        }
        return len;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1 = getLen(l1);
        int len2 = getLen(l2);
        if (len1 == 0) {
            return l2;
        } 
        if (len2 == 0) {
            return l1;
        }

        ListNode *head = NULL;
        ListNode *n1, *n2, *node;
        int gap = len1 - len2;
        if (gap > 0) {
            head = l1;
            n1=l1;
            n2=l2;
        } else {
            head = l2;
            n1=l2;
            n2=l1;
            gap=-gap;
        }

        while(gap>0) {
            n1 = n1->next;
            gap--;
        }

        while(n1) {
            n1->val += n2->val;
            n1=n1->next;
            n2=n2->next;
        }

        int val = recur(head);
        if (val > 0) {
            ListNode *tmp = new ListNode(val);
            tmp->next = head;
            head = tmp;
        }
        return head;
    }
    int recur(ListNode *node) {

        int val = 0;
        if (node->next) {
            val = recur(node->next);
        }
        node->val += val;
        if (node->val>=10) {
            val = node->val/10;
            node->val %= 10;
        } else {
            val = 0;
        }
        return val;
    }
};

